
\chapter{Environments}

\label{chapter:environments}

\section{Environments and contours}

\label{environments}

\iix{Environments} are associations between \iix{identifiers} (variable
names) and \iix{values}.  One such association between an identifier
and a value is called a \iix{binding}.  In general, environments
are created implicitly, for example, on entering {\tt LAMBDA}-bodies.
\index{variables}


Environments are organized hierarchically into \iix{contours}.  Each
contour augments an ``outer'' environment, providing bindings for a few
additional identifiers.  These bindings are in effect in the body of the
expression which introduces the contour.  The portion of a program in which
a binding is in effect is known as the variable's \iix{scope}.

For example:
{\tt \begin{tabbing}
(BLOCK \= \+ \\
 (LIST 'A 'B) \\
 \ldots\  \\
 (LAMBDA \= (A B C) \+ \\
   \ldots\                   ; [1] \\
   (LAMBDA \= (D E) \+ \\
     \ldots\                 ; [2] \\
     ()) \- \\
   \ldots\                   ; [3] \\
   (LAMBDA \= (A F G) \+ \\
     \ldots\                 ; [4] \\
     ) \- \\
   \ldots\ ) \- \\
 \ldots\ )
\end{tabbing}}
Each {\tt LAMBDA} introduces a new contour.  This code presumably occurs in
an outermost environment in which the variable {\tt LIST} is bound.
(The values of {\tt BLOCK} and {\tt LAMBDA} are not in question here;
they are reserved words, and their bindings as variables are irrelevant.)
At point {\tt [1]} in the program, a new environment is in effect
which now has bindings for {\tt A}, {\tt B}, and {\tt C}, as well as for
any variables known in the outer environment.  At {\tt [2]},
{\tt D} and {\tt E} also have values.  {\tt [3]} is in the
scope of {\tt A}, {\tt B}, and {\tt C} but not in the scope of
{\tt D} and {\tt E}.  Finally, the outer binding
of any given identifier is {\it shadowed\/}\index{shadowing}
by inner bindings of that identifier;
an occurrence of the identifier {\tt A}
appearing at {\tt [4]} refers not to the outer {\tt A}
but to the inner one, because the inner one shadows the outer.

There are two kinds of contours, known as {\it lambda-contours\/} and
{\it locales\/}.  Lambda-contours are introduced by many special forms,
such as {\tt LAMBDA}, {\tt LET}, and {\tt LABELS}.  Locales are
introduced by {\tt LOCALE} special forms.

\section{Local variables}


\index{LET@{\tt LET}}
{\mbox {\tt (LET {\it specs\/} . {\it body\/}) $\longrightarrow$\  {\it value-of-body\/}}}
\hfill Special form

\label{LET}
\begin{inset}{}

{\tt LET} provides a convenient syntax for introducing local bindings.
Each {\it spec\/} should be a two-element list of the form {\tt ({\it variable
value\/})}.  The {\it value\/} expressions are all evaluated (in no particular
order), then the
{\it body\/} (an implicit block) is evaluated in an environment where the
{\it variables\/} are bound to those values.  The value of {\it body\/} is
yielded. The result of the expression is undefined if more than one
{\it spec\/} has its first element to be the same {\it variable\/}.
\begin{codexenv}
(LET ((X 2)) X)  $\Longrightarrow$\   2 \\

(LET (({\it var$_{\hbox{1}}$ val$_{\hbox{1}}$\/}) ({\it var$_{\hbox{2}}$ val$_{\hbox{2}}$\/}) \ldots\  ({\it var$_{\hbox{n}}$ val$_{\hbox{n}}$\/})) . {\it body\/}) \\
$\equiv$ ((LAMBDA ({\it var$_{\hbox{1}}$ var$_{\hbox{2}}$\/} \ldots\  var$_{\hbox{n}}$) . {\it body\/}) {\it val$_{\hbox{1}}$ val$_{\hbox{2}}$ \ldots\  val$_{\hbox{n}}$\/})
\end{codexenv}

See also {\tt DESTRUCTURE} (page \pageref{DESTRUCTURE}).
\end{inset}

\index{LET*@{\tt LET*}}
{\mbox {\tt (LET* {\it specs\/} . {\it body\/}) $\longrightarrow$\  {\it value-of-body\/}}}
\hfill Special form

\begin{inset}{}
{\tt LET*} is like {\tt LET}, except that the binding of variables to
values is done sequentially, so that the second binding
is done in an environment in which the first binding has already occurred,
etc.  In a {\tt LET}-expression, all the bindings are done in one
environment.
For example,
suppose the variable {\tt A} is already bound to {\tt 10} when
the expression {\mbox {\tt (LET ((A 20) (B A)) B)}} is evaluated.  The
result is {\tt 10}, not {\tt 20}, because {\tt B} is bound to
{\tt A}'s value in the outer environment.  In contrast,
{\mbox {\tt (LET* ((A 20) (B A)) B)}} evaluates to {\tt 20}.

{\tt \begin{tabbing}
(LET* \= (({\it var$_{\hbox{1}}$ val$_{\hbox{1}}$\/}) ({\it var$_{\hbox{2}}$ val$_{\hbox{2}}$\/}) \ldots\  ({\it var$_{\hbox{n}}$ val$_{\hbox{n}}$\/})) . {\it body\/}) \\
  \> $\equiv$ \\
(LET \= (({\it var$_{\hbox{1}}$ val$_{\hbox{1}}$\/})) \+ \\
  (LET \= (({\it var$_{\hbox{2}}$ val$_{\hbox{2}}$\/})) \+ \\
       \ldots\  \\
       (LET (({\it var$_{\hbox{n}}$ val$_{\hbox{n}}$\/})) . {\it body\/})\ldots\ )) \- \- \\
  $\equiv$ \\
((LAMBDA \= ({\it var$_{\hbox{1}}$\/}) \+ \\
   ((LAMBDA \= ({\it var$_{\hbox{2}}$\/}) \+ \\
       \ldots\  \\
       ((LAMBDA ({\it var$_{\hbox{n}}$\/}) . {\it body\/}) \\
        {\it val$_{\hbox{n}}$\/}) \ldots\ ) \- \\
    {\it val$_{\hbox{2}}$\/})) \- \\
 {\it val$_{\hbox{1}}$\/})
\end{tabbing}}
\end{inset}

\index{LABLES@{\tt LABLES}}
{\mbox {\tt (LABELS {\it specs\/} . {\it body\/}) $\longrightarrow$\  {\it value-of-body\/}}}
\hfill Special form

\begin{inset}{}

{\tt LABELS} is useful for defining local procedures that may be
mutually recursive.
Each {\it spec\/} should be of the form
{\mbox {\tt ({\it variable value\/})}}.
The {\it value\/}-expressions are evaluated (in no particular order), and
the {\it body\/} is evaluated in an environment
where all the {\it variables\/} are bound to those values.
However, {\tt LABELS} differs from {\tt LET} in that
the bindings of the {\it variables\/} are already in effect (scope) before the
{\it value\/}-expressions are evaluated, so that the
{\it value\/}-expressions can refer to any of the {\it variables\/},
including the ones to which they themselves will be bound (thus permitting
local recursive procedures).

Each {\it spec\/} may alternatively have the form
\begin{codexenv}
{\mbox {\tt (({\it variable\/} . {\it argument-vars\/}) . {\it body\/})}}
\end{codexenv}
This is equivalent to
\begin{codexenv}
{\mbox {\tt ({\it variable\/} (LAMBDA {\it argument-vars\/} . {\it body\/}))}}
\end{codexenv}
This is intended to parallel the syntax for {\tt DEFINE} (see page
\pageref{DEFINE}).

In the following example, note that {\tt REV-1} is bound to a value that
refers to {\tt REV-1}.
{\tt \begin{tabbing}
(\= DEFINE (REVERSE L) \+ \\
  (LABELS ((\= (REV-1 L RESULT-SO-FAR) \+ \\
            (COND \= ((NULL? L) RESULT-SO-FAR) \+ \\
                  (\= ELSE \+ \\
                    (REV-1 \= (CDR L) \+ \\
                           (CONS (CAR L) RESULT-SO-FAR)))))) \- \- \- \\
    (REV-1 L '())))
\end{tabbing}}

As an extension to the dialect of SCHEME described in
\cite{rrs}, {\bf T} does not restrict the {\it value\/} expressions
to be {\tt LAMBDA}-expressions.
However, the values of the {\it variables\/}
are not defined until {\it body\/} is evaluated; i.e., the variables should
not be used in the {\it value\/}-expressions.  For example,
{\mbox {{\tt (LABELS ((A B) (B 1)) . {\it body\/})}}}
is ill-formed;
at the point when the expressions {\tt B} and {\tt 1} are being evaluated,
the variable {\tt B} is bound,
but will have an undefined value.  Consequently, {\tt A} will have an undefined
value.  By contrast, in the well-formed expression

\begin{codexenv}
(LABELS ((A (LAMBDA (X) (+ X B))) (B 1)) . {\it body\/}){\rm }
\end{codexenv}

which can also be written

\begin{codexenv}
(LABELS (((A X) (+ X B)) (B 1)) . {\it body\/}){\rm }
\end{codexenv}

the value of {\tt B} is not used before {\it body\/} is evaluated.
The {\tt LAMBDA}-expression evaluates
to a {\it closure\/} that includes {\tt B}.  By the time {\tt A} (the closure)
is called, {\tt B} will have a value.

{\tt LABELS} cannot easily be described in terms of {\tt LAMBDA}.
However, it can be described in terms of {\tt LAMBDA} and {\tt SET}.
({\tt SET} performs side-effects on bindings; see page \pageref{SET}.)
This is misleading because {\tt LABELS} should not be thought of as a
side-effecting operator.
{\tt \begin{tabbing}
(LABELS \= (\= ({\it var$_{\hbox{1}}$\/} {\it val$_{\hbox{1}}$\/}) \+ \+ \\
         ({\it var$_{\hbox{2}}$\/} {\it val$_{\hbox{2}}$\/}) \\
         \ldots\  \\
         ({\it var$_{\hbox{n}}$\/} {\it val$_{\hbox{n}}$\/})) \- \\
  . {\it body\/}) \\
   $\equiv$ \- \\
(LET \= (\= ({\it var$_{\hbox{1}}$\/} (UNDEFINED-VALUE)) \+ \+ \\
      ({\it var$_{\hbox{2}}$\/} (UNDEFINED-VALUE)) \\
      \ldots\  \\
      ({\it var$_{\hbox{n}}$\/} (UNDEFINED-VALUE))) \- \\
  (SET {\it var$_{\hbox{1}}$\/} {\it val$_{\hbox{1}}$\/}) \\
  (SET {\it var$_{\hbox{2}}$\/} {\it val$_{\hbox{2}}$\/}) \\
  \ldots\  \\
  (SET {\it var$_{\hbox{n}}$\/} {\it val$_{\hbox{n}}$\/}) \\
  . {\it body\/})
\end{tabbing}}
This equivalence is overly concrete in that the order of evaluation of
the {\it val$_{\hbox{i}}$\/} expressions, and the sequence in which the
variables are given their values, is not defined.
\end{inset}

\section{Locales}

\label{section:locale}

\begin{inset}{{\bf T3}:}
	We are working on a module system which will eventually
	subsume the functionality of {\mbox {\tt locale}}.
\end{inset}

{\it Locales\/} serve two purposes.  First, they provide an incremental or
declarative syntax for creating variable bindings in a contour.  Second,
they provide access to environments as objects which can be dynamically
manipulated.  The term \iix{locale} is used to mean both the kind of
contour introduced by a {\tt LOCALE}-expression, and the object which
represents the environment.

There are no global variables in {\bf T}; all variables are lexically
bound in some contour.  Locales play the role of what is known in other
Lisp and Scheme dialects as the global environment.

\index{DEFINE@{\tt DEFINE}}
{\mbox {\tt (DEFINE {\it variable\/} {\it value\/}) $\longrightarrow$\  {\it undefined\/}}}
\hfill Special form
\\ {\mbox {\tt (DEFINE ({\it variable\/} . {\it arguments\/}) . {\it body\/}) $\longrightarrow$\  {\it undefined}}}

\label{DEFINE}
\begin{inset}{}
{\tt DEFINE} creates a binding for {\it variable\/}
in the lexically innermost locale in which the {\tt DEFINE} expression occurs.
The variable is given {\it value\/} as its value.

The second {\tt DEFINE} syntax is for defining procedures.
\begin{codexenv}
(DEFINE ({\it variable\/} . {\it arguments\/}) . {\it body\/})
\end{codexenv}
is equivalent to
\begin{codexenv}
(DEFINE {\it variable\/} (LAMBDA {\it arguments\/} . {\it body\/}))
\end{codexenv}
For example:
\begin{codexenv}
    \begin{tabular}{lll}
(DEFINE (F X) (LIST X 2))    & $\equiv$  & (DEFINE F (LAMBDA (X) (LIST X 2))) \\
(DEFINE (F . X) (LIST X 2))  & $\equiv$  & (DEFINE F (LAMBDA X (LIST X 2)))
\end{tabular}
    \end{codexenv}
\end{inset}

\index{LSET@{\tt LSET}}
{\mbox {\tt (LSET {\it variable value\/}) $\longrightarrow$\  {\it undefined\/}}}
\hfill Special form
\\ {\mbox {\tt (LSET {\it variable value\/}) $\longrightarrow$\  {\it value\/}}}

\begin{inset}{}

The value of the {\mbox {\tt LSET}} special form is undefined, and
it is an error to use an {\mbox {\tt LSET}} form in a value requiring
position.  In {\bf T3.0}, {\mbox {\tt LSET}} will continue to return
a value, but an error will be signalled in the future.

{\tt LSET} is identical to {\tt DEFINE} except that the procedure
definition syntax is not permitted, and the variable is declared to be
alterable.  Variables bound by {\tt DEFINE} may not be altered
with {\tt SET}; variables bound by {\tt LSET} may be.
See {\tt SET}, page \pageref{SET}.
\end{inset}

\index{MAKE-LOCALE@{\tt MAKE-LOCALE}}
{\mbox {\tt (MAKE-LOCALE {\it superior-locale\/} {\it identification\/}) $\longrightarrow$\  {\it locale\/}}}
\hfill  

\label{MAKE-LOCALE}
\begin{inset}{}

Creates a locale inferior to {\it superior-locale\/}.  {\it Identification\/}
may be any object, and is used only for debugging purposes.
\begin{codexenv}
(DEFINE *FOO-ENV* (MAKE-LOCALE STANDARD-ENV '*FOO-ENV*))
\end{codexenv}
\end{inset}

\index{MAKE-EMPTY-LOCALE@{\tt MAKE-EMPTY-LOCALE}}
{\mbox {\tt (MAKE-EMPTY-LOCALE {\it identification\/}) $\longrightarrow$\  {\it locale\/}}}
\hfill  

\label{MAKE-EMPTY-LOCALE}
\begin{inset}{}
Creates a locale containing no bindings whatsoever.
\end{inset}

\index{LOCALE?@{\tt LOCALE?}}
{\mbox {\tt (LOCALE? {\it object\/}) $\longrightarrow$\  {\it boolean\/}}}
\hfill Type predicate

\begin{inset}{}
Returns true if {\it object\/} is a locale.
\end{inset}

\section{Non-local reference}


\index{*VALUE@{\tt *VALUE}}
{\mbox {\tt (*VALUE {\it locale identifier\/}) $\longrightarrow$\  {\it object\/}}}
\hfill Settable

\begin{inset}{}

Accesses the value of {\it identifier\/} in {\it locale\/}.
If {\it identifier\/} has no value in {\it locale\/}, then
the effect of the call to {\tt *VALUE} is undefined.
\begin{codexenv}
    \begin{tabular}{lll}
(*VALUE STANDARD-ENV 'T)             &  $\Longrightarrow$\  &  {\it true} \\
(LSET MY-LOCALE (MAKE-EMPTY-LOCALE 'MYSTUFF)) \\
(*DEFINE MY-LOCALE 'A 10) \\
(*VALUE MY-LOCALE 'A)  & $\Longrightarrow$\   & 10
\end{tabular}
    \end{codexenv}
\end{inset}

\index{*DEFINE@{\tt *DEFINE}}
{\mbox {\tt (*DEFINE {\it locale\/} {\it identifier\/} {\it value\/}) $\longrightarrow$\  {\it undefined\/}}}
\hfill  

\begin{inset}{}
Defines the value of {\it identifier\/} in {\it locale\/} to be {\it value\/}.
\end{inset}

\index{*LSET@{\tt *LSET}}
{\mbox {\tt (*LSET {\it locale\/} {\it identifier\/} {\it value\/}) $\longrightarrow$\  {\it value\/}}}
\hfill  

\begin{inset}{}
Creates a binding for {\it identifier\/} in {\it locale\/} with initial
value {\it value\/}.
\end{inset}

\index{IMPORT@{\tt IMPORT}}
{\mbox {\tt (IMPORT {\it locale\/} . {\it variables\/}) $\longrightarrow$\  {\it undefined\/}}}
\hfill  

\begin{inset}{}
Locally defines {\it variables\/} to have the same values as their values
in {\it locale\/}.
{\tt \begin{tabbing}
(IMPORT \= {\it locale\/} {\it var$_{\hbox{1}}$ var$_{\hbox{2}}$ \ldots\  var$_{\hbox{n}}$\/}) \\
  \> $\equiv$ \\
(BLOCK \= (DEFINE {\it var$_{\hbox{1}}$\/} (*VALUE {\it locale\/} '{\it var$_{\hbox{1}}$\/})) \+ \\
       (DEFINE {\it var$_{\hbox{2}}$\/} (*VALUE {\it locale\/} '{\it var$_{\hbox{2}}$\/})) \\
       \ldots\  \\
       (DEFINE {\it var$_{\hbox{n}}$\/} (*VALUE {\it locale\/} '{\it var$_{\hbox{n}}$\/})))
\end{tabbing}}
\end{inset}
